package com.tgy.tree;

import java.util.Comparator;
import java.util.Objects;

/**
 * @Author: tgy
 * @Date: 2020-09-23 17:56
 */
public class BinarySearchTree<E> extends BinaryTree<E>{

    private Comparator<E> comparator;

    public BinarySearchTree() {

        this(null,null);
    }

    public BinarySearchTree(Comparator<E> comparator) {
        this(comparator, null);
    }

    public BinarySearchTree(ElementOperation<E> operation) {
        this(null, operation);
    }

    public BinarySearchTree(Comparator<E> comparator,ElementOperation<E> operation) {
        super(operation);
        this.comparator = comparator;
    }

    /**
     * 添加
     * @param element
     * @return
     */
    public E add(E element) {

        if (Objects.isNull(root)) {

            root = createNode(element,null);
            size++;
            return null;
        }

        Node<E> node = root;
        int compareResult;
        Node<E> addParentNode;
        do{

            compareResult = compare(node.element, element);
            addParentNode = node;
            if (compareResult == 0) {

//                相等 则直接替换
                E tmpElement = node.element;
                node.element = element;
                return tmpElement;

            }else if (compareResult < 0) {

                node = node.right;
            }else if (compareResult > 0) {

                node = node.left;
            }
        }while (node != null);


        Node<E> newNode = createNode(element,addParentNode);

        if (compareResult > 0) {

            addParentNode.left = newNode;
        }else {

            addParentNode.right = newNode;
        }

        size++;

        addAdjust(node);

        return null;
    }

    /**
     * 调整 tree，又子类实现
     * @param node
     */
    protected void addAdjust(Node<E> node){

    }

    /**
     * 删除调整，右子类实现
     * @param node
     */
    protected void removeAdjuest(Node<E> node) {

    }

    /**
     * 创建node的对象
     * @param element
     * @param parent
     * @return
     */
    protected Node<E> createNode(E element,Node<E> parent) {

        return new Node<>(element,parent);
    }

    /**
     * 查找
     * @param element
     * @return
     */
    public E find(E element) {

        if (root == null) {

            return null;
        }

        return null;
    }

    public E remove(E element) {

        if (Objects.isNull(root)) {

            return null;
        }

        Node<E> removeNode = elementOfNode(element);

        if (Objects.isNull(removeNode)) {
            return null;
        }

        if (removeNode.degreed() == 2) {
//          如果度为2，则找到下一个后继节点，把后继节点度element值放到当前位置，删除后继节点
            Node<E> tmpNode = successorNode(removeNode);
            removeNode.element = tmpNode.element;
            removeNode = tmpNode;
        }

        if (removeNode.degreed() == 1) {
//            处理度为1的节点
            if (Objects.nonNull(removeNode.parent)) {

                if (removeNode.isLeft()) {
                    removeNode.parent.left = Objects.isNull(removeNode.left)?removeNode.right:removeNode.left;
                    removeNode.parent.left.parent = removeNode.parent;
                }else {

                    removeNode.parent.right = Objects.isNull(removeNode.left)?removeNode.right:removeNode.left;
                    removeNode.parent.right.parent = removeNode.parent;
                }

            }else {

                root = Objects.isNull(removeNode.left)?removeNode.right:removeNode.left;
                root.parent = null;
            }

        }else {
//            处理度为0的节点
            if (Objects.nonNull(removeNode.parent)) {

                if (removeNode.isLeft()) {

                    removeNode.parent.left = null;
                }else {

                    removeNode.parent.right = null;
                }

            }else {
                root = null;
            }
        }

        size--;

        removeAdjuest(removeNode);
        return element;
    }

    @Override
    public boolean contain(E element) {

        return Objects.nonNull(elementOfNode(element));
    }

    @Override
    public Node<E> elementOfNode(E element) {

        if (Objects.isNull(root)) {
            return null;
        }
        Node<E> node = root;
        int compareResult;
        do{

            compareResult = compare(node.element, element);
            if (compareResult == 0) {

                return node;
            }else if (compareResult < 0) {

                node = node.right;
            }else if (compareResult > 0) {

                node = node.left;
            }
        }while (node != null);

        return null;
    }

    private int compare(E left, E right) {

        if (this.comparator != null) {

            return comparator.compare(left, right);
        }
        return ((Comparable<E>)left).compareTo(right);
    }


}
